#include <algorithm>

using namespace std;

/* AVL 树结点 */
struct AVLTreeNode {
    int val{};             // 结点值
    int height = 0;        // 结点高度
    AVLTreeNode *left{};   // 左子结点
    AVLTreeNode *right{};  // 右子结点
    AVLTreeNode() = default;
    explicit AVLTreeNode(int x) : val(x){}
};

/* 获取结点高度 */
int height(AVLTreeNode* node) {
    // 空结点高度为 -1 ，叶结点高度为 0
    return node == nullptr ? -1 : node->height;
}

/* 更新结点高度 */
void updateHeight(AVLTreeNode* node) {
    // 结点高度等于最高子树高度 + 1
    node->height = max(height(node->left), height(node->right)) + 1;
}

/* 获取平衡因子 */
int balanceFactor(AVLTreeNode* node) {
    // 空结点平衡因子为 0
    if (node == nullptr) return 0;
    // 结点平衡因子 = 左子树高度 - 右子树高度
    return height(node->left) - height(node->right);
}
